// 动态规划思想（也是依次枚举/穷举，但把之前路径的结果缓存下来，去掉重复和不符的）
/*
大部分动态规划能解决的问题，都可以通过回溯算法来解决，只不过回溯算法解决起来效率比较低，时间复杂度是指数级O(n^2)的。
动态规划算法在执行效率方面要高很多O(n*w)。尽管执行效率提高了，但是动态规划的空间复杂度也提高了。所以，动态规划是一种空间换时间的算法思想

评论区：
贪心：一条路走到黑，就一次机会，哪边看着顺眼走哪边
回溯：一条路走下去，无数次重来的机会，还怕我走不出来
动态规划：拥有上帝视角，手握无数平行宇宙的历史存档，同时发展出无数个未来

我理解的动态规划，就是从全遍历的递归树为出发点，广度优先遍历，在遍历完每一层之后对每层结果进行合并（结果相同的）或舍弃（已经超出限制条件的），
确保下一层遍历的数量不会超过限定条件数完W，通过这个操作达到大大减少不必要遍历的目的。
在空间复杂度优化上，通过在计算中只保留最优结果的目的重复利用内存空间。
*/

#include <iostream>
#include <vector>
using std::cout;
using std::endl;

// 经典：0/1背包问题（装或不装）
/*
对于一组不同重量、不可分割的物品，我们需要选择一些装入背包。求在满足背包最大重量限制的前提下，背包能装的最大重量是多少呢？
可以假设物品重量分别为{2, 2, 4, 6, 3}，背包能容纳的最大重量为9
*/
int Knapsack1(int weightVec[], int size, int maxWeight) {
  bool* status = new bool[maxWeight + 1];  // status[0~maxWeight]是否有该重量
  for (int w = 0; w <= maxWeight; ++w) {
    status[w] = false;
  }

  status[0] = true;  // 哨兵
  if (size > 0) status[weightVec[0]] = true;
  for (int i = 1; i < size; ++i) {
    for (int w = maxWeight - weightVec[i]; w >= 0; --w) {
      // 不装，+0不用缓存
      // 装，+重量 缓存
      if (status[w]) {  // 一维数组必须从后往前，防止意外添加
        status[w + weightVec[i]] = true;
      }
    }
  }

  // print for test
  for (int w = 0; w <= maxWeight; ++w) {
    cout << status[w] << ' ';
  }
  cout << endl;
  // print for test end

  for (int w = maxWeight; w >= 0; --w) {
    if (status[w]) {
      cout << "MAX weight: " << w << endl << endl;
      return w;
    }
  }

  delete[] status;
}

void TestKnapsack1() {
  int weightVec[] = {2, 2, 4, 6, 3};
  Knapsack1(weightVec, sizeof(weightVec) / sizeof(int), 9);
}

/*
升级：在上面的基础上，假设每个物品的价值分别为{3, 4, 8, 9, 6}
求在满足背包最大重量限制的前提下，背包中物品的最大价值是多少呢？
*/
void Knapsack2(int weightVec[], int valueVec[], int size, int maxWeight) {
  std::vector<int*> status(size);  // 存储可能的累计价值
  for (int i = 0; i < size; ++i) {
    status[i] = new int[maxWeight + 1]();
  }
  // idx0:第几个物品,idx1:总重量,value:总价值。数组比map更高效，arr[idx]等价于map[key]
  status[0][0] = 0;
  if (size > 0) status[0][weightVec[0]] = valueVec[0];

  for (int i = 1; i < size; ++i) {
    for (int w = 0; w <= maxWeight; ++w) {
      if (w == 0 || status[i - 1][w] != 0) {
        int curWeight = weightVec[i] + w;
        if (curWeight > maxWeight) break;
        status[i][curWeight] =
            std::max(status[i - 1][curWeight], valueVec[i] + status[i - 1][w]);
      }
    }
  }

  // print for test
  for (int i = 0; i < size; i++) {
    for (int j = 0; j <= maxWeight; j++) {
      cout << status[i][j] << ' ';
    }
    cout << endl;
  }
  // print for test end

  int maxValue = -1;
  int maxCol = -1;
  for (int w = 0; w <= maxWeight; ++w) {
    if (status[size - 1][w] > maxValue) {
      maxValue = status[size - 1][w];
      maxCol = w;
    }
  }
  cout << "MAX value: " << maxValue << endl << endl;

  /*
  再升级：求最大价值时都装了哪些物品？
  */
  int j = maxCol;
  for (int i = size - 1; i > 0; --i) {
    int lastWeight = j - weightVec[i];
    if (lastWeight >= 0 &&
        status[i - 1][lastWeight] + valueVec[i] == status[i][j]) {
      cout << "put#" << i << " weight:" << weightVec[i]
           << ",value:" << valueVec[i] << endl;
      j = lastWeight;
    } else {
      cout << "not put#" << i << endl;
    }
  }
  if (j != 0) {
    cout << "put#" << 0 << " weight:" << weightVec[0]
         << ",value:" << valueVec[0] << endl;
  } else {
    cout << "not put#" << 0 << endl;
  }

  for (int i = 0; i < status.size(); ++i) {
    delete status[i];
  }
}

void TestKnapsack2() {
  int weightVec[] = {2, 2, 4, 6, 3};
  int valueVec[] = {3, 4, 8, 9, 6};
  Knapsack2(weightVec, valueVec, sizeof(weightVec) / sizeof(int), 9);
}

int main() {
  TestKnapsack1();
  TestKnapsack2();
}